package sword_to_1;

import java.util.HashMap;
import java.util.Map;

public class LeeCode_10_2 {
    public static void main(String[] args) {
        System.out.println(numWays(100));
    }
    private static int numWays(int n) {
        if (n == 0)
            return 1;
        return (int) (numWays2(n, new HashMap<>()));
    }
    private static long numWays2(long n, Map<Long, Long> map)  {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        if (map.containsKey(n)){
            return map.get(n);
        }
        long ans = numWays2(n - 1, map) + numWays2(n - 2, map);
        ans = ans > 1000000007 ? ans % 1000000007 : ans;
        map.put(n, ans);
        return ans;
    }
}
